package Hot100;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-12-25 16:59
 */
public class largestRectangleArea84 {

    /**84. 柱状图中最大的矩形
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 单调栈，从左向右，记录i前面第一个比i小的位置，从右向左，记录i后面第一个比i小的位置
     * */
    public int largestRectangleArea(int[] heights) {
        int n=heights.length;
        int res=0;
        int[] left=new int[n];
        int[] right=new int[n];
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i]=(stack.isEmpty()?-1:stack.peek());
            stack.push(i);
        }
        stack.clear();
        for (int i = n-1; i >=0; i--) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=(stack.isEmpty()?n:stack.peek());
            stack.push(i);
        }
        for (int i = 0; i < n; i++) {
            res=Math.max(res,(right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        largestRectangleArea84 obj=new largestRectangleArea84();
        int[] heights = {2,4};
        System.out.println(obj.largestRectangleArea(heights));
    }
}
